package Subject;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 难度：困难
 * 
 * 188. 买卖股票的最佳时机 IV 
 * 	给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
 * 	设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。 
 * 	注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * 
 * 示例 1： 
 * 	输入：k = 2, prices = [2,4,1] 
 * 	输出：2 
 * 	解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天(股票价格= 4) 的
 * 		时候卖出，这笔 交易所能获得利润 = 4-2 = 2 。
 *
 * 示例 2： 
 * 	输入：k = 2, prices = [3,2,6,5,0,3] 
 * 	输出：7 
 * 	解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天(股票价格 = 6) 的
 * 		时候卖出, 这 笔交易所能获得利润 = 6-2 = 4 。随后，在第 5 天 (股票价格 = 0) 
 * 		的时候买入， 在第 6 天(股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。
 *
 * 提示： 
 * 	0 <= k <= 10^9 
 * 	0 <= prices.length <= 1000 
 * 	0 <= prices[i] <= 1000
 *
 */

public class StockMaxProfit4 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		StockMaxProfit4 smp = new StockMaxProfit4();
		int[] prices = { 3,3,5,0,0,3,1,4 };
		int k = 2;
		System.out.println(smp.maxProfit(k, prices));
	}

	public int maxProfit(int k, int[] prices) {
		List<List<Integer>> lists = new ArrayList<List<Integer>>();
		List<Integer> list = new ArrayList<Integer>();
		List<Integer> sign = new ArrayList<Integer>();
		int count = 0;

		for (int i = 1; i < prices.length; i++) {
			// 判断是否在递增区间
			if (prices[i] > prices[i - 1]) {
				if (!list.contains(prices[i - 1])) {
					list.add(prices[i - 1]);
				}
				list.add(prices[i]);
			} else if (!list.isEmpty()) {
				// 把递增区间放进lists
				lists.add(list);
				list = new ArrayList<Integer>();
			}
			if (i == prices.length - 1 && !lists.contains(list) && !list.isEmpty()) {
				lists.add(list);
				list = new ArrayList<Integer>();
			}
		}
		while (lists.size() > k) {
			System.out.println(lists);
			int min = 0;
			int indexOf = 0;
//			for(int i=0;i<lists.size()-1;i++) {
//				min = min>lists.get(i).get(0)?lists.get(i).get(0):min;
//				indexOf=min==lists.get(i).get(0)?i:indexOf;
//			}
			for (int i = 0; i < lists.size(); i++) {
				int x = lists.get(i).get(lists.get(i).size() - 1) - lists.get(i).get(0);
				if(i==0) {
					min=x;
				}
				min = min > x ? x : min;
				indexOf = min == x ? i : indexOf;
				System.out.println(indexOf);
			}
			
			if(indexOf<lists.size()-1) {
				for (int i = 0; i < lists.get(indexOf + 1).size(); i++) {
					lists.get(indexOf).add(lists.get(indexOf + 1).get(i));
				}
				lists.remove(indexOf + 1);
			}else {
				lists.remove(indexOf);
			}
			
		}
		System.out.println(lists);
		for (List<Integer> l : lists) {
			// 因为是递增区间，最后一个数-第一个数（即最大值-最少值）
//			int i = l.get(l.size() - 1) - l.get(0);
			int max = Collections.max(l);
			int min = 0;
			while (true) {
				min = Collections.min(l);
				if (l.indexOf(max) > l.indexOf(min)) {
					break;
				} else {
					l.remove(l.indexOf(min));
					min = Collections.min(l);
				}
			}
			int i = max - min;
			sign.add(i);
		}
		System.out.println(sign);
		for (int i = 0; i < k; i++) {
			int x = 0;
			if (sign.size() > 1) {
				x = Collections.max(sign);
			} else if (sign.size() == 1) {
				x = sign.get(0);
				count += x;
				return count;
			} else {
				return count;
			}
			sign.remove(sign.indexOf(x));
			count += x;
		}
		return count;
	}

	public int maxProfit1(int k, int[] prices) {
		int[][] buy = new int[prices.length][10];
		int[][] sell = new int[prices.length][10];

		for (int i = 0; i < prices.length; i++) {

//			buy[i][]=Math.max(buy[i-1][j], sell[i-1][j]-prices[i]);
		}

		return 0;
	}
}
